//动态顺序表
#include <iostream>
#include "rrand.h"
using namespace std;
typedef int ElemType;
typedef struct sqllist
{
    ElemType *data;//数据域
    int size;//表长
    int max_size;//顺序表的最大长度
}sqllist;
//顺序表的初始化函数
void init_sqllist(sqllist &l){
    l.data=new ElemType[4];
    l.size=0;
    l.max_size=4;
    cout<<"顺序表初始化完成"<<endl;
}
//顺序表的增长函数
void increase_sqllist(sqllist &l){
    ElemType *new_data=new ElemType[l.max_size*2];
    for(int i=0;i<l.size;i++){
        new_data[i]=l.data[i];
    }
    delete[] l.data;
    l.data=new_data;
    l.max_size*=2;
}
//顺序表的释放函数
void Clear_sqllist(sqllist &l){
    delete[] l.data;
    l.size=0;
}
//顺序表的插入函数
void interposition_sqllist(sqllist &l,int num,int m=0){
    if(l.size==l.max_size){
        increase_sqllist(l);
    }
    else if(m>l.max_size){
        cout<<"插入位置非法"<<endl;
    }
    else{
        for(int i=l.size-1;i>=m;i--){
            l.data[i+1]=l.data[i];
        }
        l.data[m]=num;
        l.size++;
        cout<<"元素"<<num<<"插入完成"<<endl;
    }
}
//顺序表的查找函数
int index_sqllist(sqllist &l,int num){
    for(int i=0;i<l.size;i++){
        if(num==l.data[i])return i;
    }
    return -1;
}
//顺序表的修改函数
void edit_sqllist(sqllist &l,int num){
    int index=index_sqllist(l,num);
    if(index==-1){
        cout<<"你所要修改的元素不在顺序表中"<<endl;
    }
    else{
        int n;
        cout<<"请输入修改之后的数字>>";cin>>n;
        l.data[index]=n;
        cout<<"修改完成"<<endl;
    }
}
//顺序表的删除函数
void pop_sqllist(sqllist &l,int num){
    int index=index_sqllist(l,num);
    if(index==-1)cout<<"元素"<<num<<"不在顺序表中无法删除"<<endl;
    else{
        for(int i=index;i<l.size;i++){
            l.data[i]=l.data[i+1];
        }
        l.size--;
        cout<<"删除完成"<<endl;
    }
}
//顺序表的输出函数
void prtint_sqllist(sqllist &l){
    for(int i=0;i<l.size;i++){
        cout<<l.data[i]<<" ";
    }
    cout<<endl;
}
// 菜单
void menu()
{
    cout << "1.插入" << endl;
    cout << "2.删除" << endl;
    cout << "3.查找" << endl;
    cout << "4.修改" << endl;
    cout << "5.顺序表输出" << endl;
    cout << "0.退出" << endl;
}

// 左移运算符的重载
ostream& operator<<(ostream &cout, sqllist &l)
{
    cout << "当前顺序表中的元素为>>";
    for (int i = 0; i < l.size; i++)
    {
        cout << l.data[i] << " ";
    }
    cout << endl;
    cout << "顺序表的表长是>>" << l.size << endl;
    cout << "当前顺序表的最大长度是>>" << l.max_size;
    return cout;
}
int main()
{
    sqllist l;
    init_sqllist(l);
    int input;
    int index,num1, m1,num2,num3,num4;
    menu();
    do
    {
        cout << "请输入操作数>>";cin >> input;
        switch (input)
        {
        case 1:
            cout << "请输入插入元素>>";cin >> num1;
            cout << "请输入插入位置>>";cin >> m1;
            interposition_sqllist(l, num1, m1);
            break;
        case 2:
            cout << "请输入你所要删除的元素>>";cin >> num2;
            pop_sqllist(l, num2);
            break;
        case 3:
            cout << "请输入所要查找元素>>";cin >> num3;
            index = index_sqllist(l, num3);
            if (index == -1){
                cout << "元素" << num3 << "不在顺序表内" << endl;
            }
            else{
                cout << "元素" << num3 << "在顺序表中，下标为>>" << index << endl;
            }
            break;
        case 4:
            cout << "请输入所要修改的元素>>";cin >> num4;
            edit_sqllist(l, num4);
            break;
        case 5:
            cout << l << endl;
            break;
        case 0:
            cout << "欢迎下次使用" << endl;
            break;
        }
    }while(input);
    Clear_sqllist(l); // 释放动态顺序表的内存空间
    return 0;
}